/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

#include "infra/InterferenceGraph.hpp"

#include <stdint.h>
#include <string.h>
#include "env/StackMemoryRegion.hpp"
#include "compile/Compilation.hpp"
#include "env/TRMemory.hpp"
#include "infra/Array.hpp"
#include "infra/Assert.hpp"
#include "infra/BitVector.hpp"
#include "infra/IGBase.hpp"
#include "infra/IGNode.hpp"
#include "infra/List.hpp"
#include "infra/Stack.hpp"

TR_InterferenceGraph::TR_InterferenceGraph(TR::Compilation *comp, int32_t estimatedNodes)
    : _compilation(comp)
    , _nodeTable(NULL)
    , _nodeStack(NULL)
    , _trMemory(comp->trMemory())
    , TR_IGBase()
{
    TR_ASSERT(estimatedNodes > 0, "interference graph must be created with a node estimate!");

    int32_t numBits = (estimatedNodes * (estimatedNodes - 1)) >> 1;
    setInterferenceMatrix(new (trHeapMemory()) TR_BitVector(numBits, trMemory(), heapAlloc, growable));
    _nodeTable = new (trHeapMemory()) TR_Array<TR_IGNode *>(trMemory(), estimatedNodes, false, heapAlloc);
    _nodeStack = new (trHeapMemory()) TR_Stack<TR_IGNode *>(trMemory(), estimatedNodes, false, heapAlloc);

    // TODO: allocate from stack memory
    //
    _entityHash._numBuckets = 73;
    _entityHash._buckets
        = (HashTableEntry **)trMemory()->allocateHeapMemory(_entityHash._numBuckets * sizeof(HashTableEntry *));
    memset(_entityHash._buckets, 0, _entityHash._numBuckets * sizeof(HashTableEntry *));
}

// Add a new, unique entity to the interference graph.
//
TR_IGNode *TR_InterferenceGraph::add(void *entity, bool ignoreDuplicates)
{
    TR_IGNode *igNode = getIGNodeForEntity(entity);

    if (igNode != NULL && ignoreDuplicates)
        return igNode;

    TR_ASSERT(!igNode, "entity %p already exists in this interference graph\n", entity);

    igNode = new (trHeapMemory()) TR_IGNode(entity, trMemory());

    addIGNodeToEntityHash(igNode);

    igNode->setIndex(getNumNodes());
    ((*_nodeTable)[getNumNodes()]) = igNode;
    incNumNodes();

    return igNode;
}

// Add an interference between two existing entities in an interference graph.
//
void TR_InterferenceGraph::addInterferenceBetween(TR_IGNode *igNode1, TR_IGNode *igNode2)
{
    IMIndex bitNum = getNodePairToBVIndex(igNode1->getIndex(), igNode2->getIndex());
    if (igNode1 != igNode2 && !getInterferenceMatrix()->isSet(bitNum)) {
        getInterferenceMatrix()->set(bitNum);
        igNode2->getAdjList().add(igNode1);
        igNode1->getAdjList().add(igNode2);
        igNode2->incDegree();
        igNode1->incDegree();
    }
}

bool TR_InterferenceGraph::hasInterference(void *entity1, void *entity2)
{
    TR_IGNode *igNode1 = getIGNodeForEntity(entity1);
    TR_IGNode *igNode2 = getIGNodeForEntity(entity2);

    TR_ASSERT(igNode1, "hasInterference: entity1 %p does not exist in this interference graph\n", entity1);
    TR_ASSERT(igNode2, "hasInterference: entity2 %p does not exist in this interference graph\n", entity2);

    IMIndex bit = getNodePairToBVIndex(igNode1->getIndex(), igNode2->getIndex());
    return getInterferenceMatrix()->isSet(bit);
}

void TR_InterferenceGraph::removeInterferenceBetween(TR_IGNode *igNode1, TR_IGNode *igNode2)
{
    igNode1->getAdjList().remove(igNode2);
    igNode2->getAdjList().remove(igNode1);
    igNode1->decDegree();
    igNode2->decDegree();
    IMIndex bit = getNodePairToBVIndex(igNode1->getIndex(), igNode2->getIndex());
    getInterferenceMatrix()->reset(bit);
}

void TR_InterferenceGraph::removeAllInterferences(void *entity)
{
    TR_IGNode *igNode = getIGNodeForEntity(entity);

    TR_ASSERT(igNode, "removeAllInterferences: entity %p is not in the interference graph\n", entity);

    ListIterator<TR_IGNode> iterator(&igNode->getAdjList());
    TR_IGNode *cursor = iterator.getFirst();
    IMIndex bit;

    while (cursor) {
        cursor->getAdjList().remove(igNode);
        cursor->decDegree();
        bit = getNodePairToBVIndex(igNode->getIndex(), igNode->getIndex());
        getInterferenceMatrix()->reset(bit);
        cursor = iterator.getNext();
    }

    // reset working degree?

    igNode->setDegree(0);
    igNode->getAdjList().deleteAll();
}

void TR_InterferenceGraph::addIGNodeToEntityHash(TR_IGNode *igNode)
{
    void *entity = igNode->getEntity();

    TR_ASSERT(entity, "addIGNodeToEntityHash: IGNode %p does not reference its data\n", igNode);

    int32_t hashBucket = entityHashBucket(entity);

    // TODO: allocate from stack memory
    //
    HashTableEntry *entry = (HashTableEntry *)trMemory()->allocateHeapMemory(sizeof(HashTableEntry));
    entry->_igNode = igNode;

    HashTableEntry *prevEntry = _entityHash._buckets[hashBucket];
    if (prevEntry) {
        entry->_next = prevEntry->_next;
        prevEntry->_next = entry;
    } else
        entry->_next = entry;

    _entityHash._buckets[hashBucket] = entry;
}

TR_IGNode *TR_InterferenceGraph::getIGNodeForEntity(void *entity)
{
    int32_t hashBucket = entityHashBucket(entity);

    HashTableEntry *firstEntry = _entityHash._buckets[hashBucket];
    if (firstEntry) {
        HashTableEntry *entry = firstEntry;

        do {
            if (entry->_igNode->getEntity() == entity) {
                return entry->_igNode;
            }
            entry = entry->_next;
        } while (entry != firstEntry);
    }

    return NULL;
}

// Doesn't actually remove a node from the IG, but adjusts the working degrees of its
// neighbours and itself to appear that way.
//
void TR_InterferenceGraph::virtualRemoveEntityFromIG(void *entity)
{
    TR_IGNode *igNode = getIGNodeForEntity(entity);
    igNode->decWorkingDegreeOfNeighbours();
    igNode->setIsRemovedFromIG();
    igNode->setWorkingDegree(0);
}

// Doesn't actually remove a node from the IG, but adjusts the working degrees of its
// neighbours and itself to appear that way.
//
void TR_InterferenceGraph::virtualRemoveNodeFromIG(TR_IGNode *igNode)
{
    igNode->decWorkingDegreeOfNeighbours();
    igNode->setIsRemovedFromIG();
    igNode->setWorkingDegree(0);
}

// Partition the nodes identified by the 'workingSet' bit vector into sets
// based on their degree.
//
void TR_InterferenceGraph::partitionNodesIntoDegreeSets(TR_BitVector *workingSet, TR_BitVector *colourableDegreeSet,
    TR_BitVector *notColourableDegreeSet)
{
    int32_t i;
    TR_BitVectorIterator bvi(*workingSet);

    TR_ASSERT(getNumColours() > 0, "can't partition without knowing the number of available colours\n");

    // Empty the existing degree sets.
    //
    colourableDegreeSet->empty();
    notColourableDegreeSet->empty();

    // Partition the specified nodes into sets based on their working degree.
    //
    while (bvi.hasMoreElements()) {
        i = bvi.getNextElement();

        if (getNodeTable(i)->getWorkingDegree() < unsigned(getNumColours())) {
            colourableDegreeSet->set(i);
        } else {
            notColourableDegreeSet->set(i);
        }
    }

#ifdef DEBUG
    if (debug("traceIG")) {
        diagnostic("\nPartitioned Nodes\n");
        diagnostic("-----------------\n");

        diagnostic("\n[%4d] degree < %-10d : ", colourableDegreeSet->elementCount(), getNumColours());
        colourableDegreeSet->print(comp());

        diagnostic("\n[%4d] degree < MAX_DEGREE : ", notColourableDegreeSet->elementCount());
        notColourableDegreeSet->print(comp());
        diagnostic("\n\n");
    }
#endif
}

IGNodeDegree TR_InterferenceGraph::findMaxDegree()
{
    IGNodeDegree maxDegree = 0;

    for (IGNodeIndex i = 0; i < getNumNodes(); i++) {
        if (getNodeTable(i)->getDegree() > maxDegree) {
            maxDegree = getNodeTable(i)->getDegree();
        }
    }

    return maxDegree;
}

// General Briggs graph colouring algorithm.
//
bool TR_InterferenceGraph::doColouring(IGNodeColour numColours)
{
    bool success;

    TR::StackMemoryRegion stackMemoryRegion(*trMemory());

    TR_ASSERT(numColours > 0, "doColouring: invalid chromatic number\n");
    setNumColours(numColours);

    // TODO: reset stacks, colours?
    //
    if ((success = simplify())) {
        success = select();
    }

    if (debug("traceIG")) {
        if (!success) {
            diagnostic("COLOUR IG: Could not find a colouring for IG %p with %d colours.\n", this, numColours);
        } else {
            diagnostic("COLOUR IG: IG %p coloured with %d colours.\n", this, getNumberOfColoursUsedToColour());
        }
    }

    return success;
}

// Find the minimum number of colours required to colour this interference graph.
//
IGNodeColour TR_InterferenceGraph::findMinimumChromaticNumber() { return 0; }

// Perform Simplify colouring phase on an interference graph.
//
bool TR_InterferenceGraph::simplify()
{
    TR_IGNode *igNode, *bestSpillNode;

    if (getNumNodes() == 0)
        return true;

    TR_BitVector *workingSet = new (trStackMemory()) TR_BitVector(getNumNodes(), trMemory(), stackAlloc);
    workingSet->setAll(getNumNodes());

    TR_BitVector *colourableDegreeSet = new (trStackMemory()) TR_BitVector(getNumNodes(), trMemory(), stackAlloc);
    TR_BitVector *notColourableDegreeSet = new (trStackMemory()) TR_BitVector(getNumNodes(), trMemory(), stackAlloc);

    for (auto i = 0U; i < getNumNodes(); i++) {
        igNode = getNodeTable(i);
        igNode->setWorkingDegree(igNode->getDegree());
        igNode->resetIsRemovedFromIG();
        igNode->setColour(UNCOLOURED);
    }

    while (!workingSet->isEmpty()) {
        partitionNodesIntoDegreeSets(workingSet, colourableDegreeSet, notColourableDegreeSet);

        // Push nodes from the colourable set onto the stack and adjust the degrees of
        // their neighbours until there are no nodes remaining in the colourable set.
        //
        if (!colourableDegreeSet->isEmpty()) {
            TR_BitVectorIterator bvi(*colourableDegreeSet);

            while (bvi.hasMoreElements()) {
                igNode = getNodeTable(bvi.getNextElement());

                if (debug("traceIG")) {
                    diagnostic("SIMPLIFY: Selected colourable IG node #%d with degree %d: (igNode=%p, entity=%p)\n",
                        igNode->getIndex(), igNode->getWorkingDegree(), igNode, igNode->getEntity());
                }

                virtualRemoveNodeFromIG(igNode);
                workingSet->reset(igNode->getIndex());
                getNodeStack()->push(igNode);
            }

            // Repartition the nodes.
            //
            continue;
        }

        // There are no nodes left in the colourable set.  Choose a spill candidate among nodes in
        // the non-colourable degree set.
        //
        TR_ASSERT(!notColourableDegreeSet->isEmpty(), "not colourable set must contain at least one member\n");

        TR_BitVectorIterator bvi;
        if (!notColourableDegreeSet->isEmpty()) {
            // Choose the node from this degree set with the largest degree
            // and optimistically push it onto the stack.
            //
            int32_t degree = -1;

            bestSpillNode = NULL;
            while (bvi.hasMoreElements()) {
                igNode = getNodeTable(bvi.getNextElement());

                // TODO: This unsigned conversion was inserted while addressing warnings. The warning at this line
                // warned us about signed/unsigned comparison. The C++ standard dictates that signed values are always
                // converted to unsigned before the comparison. Because `degree` is initialized to -1, the unsigned
                // conversion will produce UINT_MAX in this case, so the comparison below will never succeed and we
                // should always assert.
                if (igNode->getDegree() > unsigned(degree)) {
                    degree = igNode->getDegree();
                    bestSpillNode = igNode;
                }
            }

            TR_ASSERT_FATAL(bestSpillNode, "Could not find a spill candidate");

            virtualRemoveNodeFromIG(bestSpillNode);
            workingSet->reset(bestSpillNode->getIndex());
            getNodeStack()->push(bestSpillNode);
        }
    }

    return true;
}

// Perform Select colouring phase on an interference graph.
//
bool TR_InterferenceGraph::select()
{
    TR_IGNode *igNode;
    TR_BitVectorIterator bvi;

    TR_BitVector *availableColours = new (trStackMemory()) TR_BitVector(getNumColours(), trMemory(), stackAlloc);
    TR_BitVector *assignedColours = new (trStackMemory()) TR_BitVector(getNumColours(), trMemory(), stackAlloc);

    setNumberOfColoursUsedToColour(0);

    while (!getNodeStack()->isEmpty()) {
        igNode = getNodeStack()->pop();

        availableColours->setAll(getNumColours());

        ListIterator<TR_IGNode> iterator(&igNode->getAdjList());
        TR_IGNode *adjCursor = iterator.getFirst();

        while (adjCursor) {
            if (adjCursor->getColour() != UNCOLOURED) {
                availableColours->reset(adjCursor->getColour());
            }

            adjCursor = iterator.getNext();
        }

        if (debug("traceIG")) {
            diagnostic("SELECT:  For IG node #%d (%p), available colours = ", igNode->getIndex(), igNode);
            availableColours->print(_compilation->log(), _compilation);
            diagnostic("\n");
        }

        bvi.setBitVector(*availableColours);

        if (bvi.hasMoreElements()) {
            IGNodeColour colour = (IGNodeColour)bvi.getNextElement();
            igNode->setColour(colour);

            if (!assignedColours->isSet(colour)) {
                assignedColours->set(colour);
            }

            if (debug("traceIG")) {
                diagnostic("         Selected colour: %d\n", colour);
            }
        } else {
            // No colours are available.  Colouring has failed.
            //
            if (debug("traceIG")) {
                diagnostic("         NO COLOURS AVAILABLE\n");
            }

            return false;
        }
    }

    setNumberOfColoursUsedToColour(assignedColours->elementCount());
    return true;
}

#ifdef DEBUG
void TR_InterferenceGraph::dumpIG(const char *msg)
{
    if (msg) {
        diagnostic("\nINTERFERENCE GRAPH %p: %s\n\n", this, msg);
    } else {
        diagnostic("\nINTERFERENCE GRAPH %p\n\n", this);
    }

    for (IGNodeIndex i = 0; i < getNumNodes(); i++) {
        getNodeTable(i)->print(comp());
    }
}
#endif
